[USACO03FALL]Cow Exhibition G
题意
给定 个数分别有 个权值 ,选取一些数使得 的条件下求 的最大值。
Nothing with me, but Forever.
给定 n 个数分别有 2 个权值 ai,bi,选取一些数使得 ∑ai≥0,∑bi≥0 的条件下求 ∑ai+bi 的最大值。
存在依赖关系背包转化分组背包。
给定 n 个物品的价值和体积,他们之间存在简单的依赖关系,即一个结点要么是父亲结点,要么是儿子结点,且一个父亲结点最多有两个儿子结点。
考虑现在有 n 本书并给定一个最大长度 L,第 i 本书有高度 hi,wi。每次选取一段范围满足该段范围内的所有书的 ∑wi≤L,那么这次选取的贡献为 max{hi}。
给定的数据范围是一个弱化版本。
给定 n 个点权 {a},并按照规则:对于 i,j,如果 i&j=0 则对 i,j 连边,生成图 G。
现在要求 G 中的每个点都要按照如下规则加入集合 S:
求最大贡献,n≤2×103,ai≤109。
给定一棵有 n 个结点的树,每次操作选取 3 个点 i,j,k 满足 i,j 存在连边,j,k 存在连边,定义一次操作为:
求最小的操作次数使得树存在度为 n−1 的点。
现在给定一个序列 {a},令 f(i,j)=j−iai×aj。对于每个 i,计算出所有满足 j≤i×k 的 f(i,j),(其中 k 为一个小于 0.35 的常量),相对误差小于 5%。